import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:
 * Date: 2024-10-13
 * Time: 10:55
 */
public class Sort {
    public static void quickSort(int[] array){
        quickNor(array,0,array.length-1);
    }

    private static void quickNor(int[] array, int start, int end){

        Deque<Integer> stack = new ArrayDeque<>();
        int pivot = partition1(array, start, end);
        //pivot左边有两个元素
        if(pivot > start+1){
            stack.push(start);
            stack.push(pivot-1);
        }

        if(pivot < end-1){
            stack.push(pivot+1);
            stack.push(end);
        }

        while(!stack.isEmpty()){
            end = stack.pop();
            start = stack.pop();
            pivot = partition1(array, start, end);
            if(pivot > start+1){
                stack.push(start);
                stack.push(pivot-1);
            }

            if(pivot < end-1){
                stack.push(pivot+1);
                stack.push(end);
            }
        }
    }

    private static void quick(int[] array, int start, int end){
        // = 是为了应对没有右边的情况，递归结束条件
        if(start >= end){
            return;
        }

        if(end - start + 1 <= 7){
            insertSortRange(array, start, end);
            return;
        }
        int minIndex = getMiddleNum(array, start, end);
        swap(array, start, minIndex);

        //整个方法走完之后，为第一次交换位置
        int pivot = partition1(array, start, end);
        quick(array, start, pivot-1);
        quick(array, pivot+1, end);
    }

    public static void insertSortRange(int[] array, int start, int end){
        for (int i = start+1; i <= end; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= start; j--) {
                if(array[j] > tmp){
                    array[j+1] = array[j];
                }else{
                    array[j+1] = tmp;
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    private static int getMiddleNum(int[] array, int left, int right){
        int mid = (left+right)/2;
        if(array[left] < array[right]){
            if(array[mid] < array[left]){
                return left;
            }else if(array[mid] > array[right]){
                return right;
            }else{
                return mid;
            }
        }else{
            if(array[mid] > array[left]){
                return left;
            }else if(array[mid] < array[right]){
                return right;
            }else{
                return mid;
            }
        }
    }

    private static int partition1(int[] array, int left, int right) {
        int tmp = array[left];

        while(left < right){
            //循环找，不循环时则代表找到，找到比tmp小的数
            while(left < right && array[right] >= tmp){
                right--;
            }
            //挖坑法，然后填坑
            //先是把第一个位置当作空，从后面数，如果有数比它小，就放到第一位
            //然后是从前数，找最大值，找到后放到，刚刚的位置
            //最后再把第一个数放到right和left相交的位置
            //方法就是把两边的数分大小放到第一个数两边
            array[left] = array[right];


            //找到比tmp大的数
            while(left < right && array[left] <= tmp){
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }

    private static void swap(int[] array, int left, int right){
        int tmp = array[left];
        array[left] = array[right];
        array[right] = tmp;
    }

    /**
     * 时间复杂度：O(N*logN)
     * 空间复杂度：O(N)
     * 稳定性：稳定
     * @param array
     */
    public static void mergeSort(int[] array){
        mergeSortTmp(array, 0, array.length-1);
    }

    private static void mergeSortTmp(int[] array, int left, int right) {
        if(left >= right){
            return;
        }
        int mid = (left + right)/2;
        mergeSortTmp(array, left, mid-1);
        mergeSortTmp(array, mid+1, right);
        //走到这里，相当于全部分解完
        //合并，合并有序数组
        merge(array, left, mid, right);


    }

    private static void merge(int[] array, int left, int mid, int right) {
        int[] tmp = new int[right-left+1];
        int k = 0;
        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;

        while(s1 <= e1 &&  s2 <= e2){
            if(array[s1] <= array[s2]){
                tmp[k++] = array[s1++];
            }else {
                tmp[k++] = array[s2++];
            }
        }

        while(s1 <= e1){
            tmp[k++] = array[s1++];
        }

        while(s2 <= e2){
            tmp[k++] = array[s2++];
        }
        //可以保证tmp数组是有序的
        for (int i = 0; i < k; i++) {
            array[i+left] = tmp[i];
        }
    }

    public static void mergeSortNor(int[] array){
        int gap =1;
        while(gap < array.length){
            for (int i = 0; i < array.length; i = i + gap*2) {
                int left = i;
                int mid = (left + gap -1);
                if(mid >= array.length){
                    mid = array.length-1;
                }
                int right = mid + gap;
                if(right >= array.length){
                    right = array.length-1;
                }
                merge(array, left, mid, right);
            }
            gap *= 2;
        }
    }

    /**
     * 计数数组
     * 时间复杂度：O(范围 + N),范围越大，时间复杂第越大
     * 空间复杂度：O(范围)
     * 稳定性：现在代码不稳定
     * @param array
     */
    public static void countSort(int[] array){

        //1.找最大值 和 最小值 来确定 计数数组的大小
        int maxVal = array[0];
        int minVal = array[0];
        for (int i = 1; i < array.length; i++) {
            if(array[i] > maxVal){
                maxVal = array[i];
            }
            if(array[i] < minVal){
                minVal = array[i];
            }
        }
        int len = maxVal - minVal + 1;
        int[] count = new int[len];

        //2.遍历原来的数组array， 把每个元素 放到对应的计数数组中 进行比较
        for (int i = 0; i < array.length; i++) {
            int index = array[i];
            count[index-minVal]++;
        }

        //3.依次 遍历计数数组 时间复杂度:O(范围)
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while(count[i] != 0){
                array[index] = i+minVal;
                index++;
                count[i]--;
            }
        }
    }
}
